// 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

// 注意:
// 可以认为区间的终点总是大于它的起点。
// 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

const eraseOverlapIntervals = function (intervals: number[][]): number {
    // 安全检测
    if (intervals.length < 1) {
        return 0;
    }
    // 根据结束的区间排序
    intervals.sort((a, b) => a[1] - b[1]);
    let removeCount: number = 0; // 移除数量
    let currRightBound: number = intervals[0][1];// 当前右边界
    for (let i = 1; i < intervals.length; i++) {
        // 如果当前元素的左边界比当前最小右边界小，说明发生了重叠需要移除
        if (intervals[i][0] < currRightBound) {
            removeCount++;
        } else {
            currRightBound = intervals[i][1];
        }
    }
    return removeCount;
};

eraseOverlapIntervals([
    [1, 100],
    [11, 22],
    [1, 11],
    [2, 12]
])


// 这道题目属于非常经典的区间调度类型的题目
// 这道题直面去理解其实并不直观，我们可以把“找到需要移除区间的最小数量，使剩余区间互不重叠”这个要求
// 翻译成“设计一个算法，求出这些区间中最多有几个互不相交的区间”
// 而这道题目又有一个现实语境下的理解：
// 比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间，
// 请问你今天最多能参加几个活动呢？
// 显然你一个人不能同时参加两个活动，所以说这个问题就是求这些时间区间的最大不相交子集。
// 而正确的思路应该是：
// 1. 从区间集合中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
// 2. 把所有与 x 区间相交的区间从区间集合计数。
// 3. 重复步骤 1 和 2，直到扫描结束
// 把这个思路实现成算法的话，可以按每个区间的 end 数值升序排序即可

// 这里还有一个有意思的地方：为什么按照end排序，而不是按照start排序？
// 解释是：比如你一天要参加几个活动，这个活动开始的多早其实不重要，重要的是你结束的多早
// 早晨7点就开始了然后一搞搞一天，那你今天也就只能参加这一个活动
// 但如果这个活动开始的不早，比如9点才开始，但是随便搞搞10点就结束了
// 那你接下来就还有大半天的时间可以参加其他活动。
// 这就是为啥要着眼于end，而不是start。0